We present a detailed analysis of two-band HST/ACS imaging of 21 ultra-compact dwarf (UCD) galaxies in the Virgo and Fornax Clusters. The aim of this work is to test two formation hypotheses for UCDs--whether they are bright globular clusters (GCs) or "threshed'' early-type dwarf galaxies--by comparison of UCD structural parameters and colors with GCs and galaxy nuclei. We find that the UCD surface brightness profiles can be described by a range of models and that the luminous UCDs can not be described by standard King models with tidal cutoffs as they have extended outer halos. This is not expected from traditional King models of GCs, but is consistent with recent results for massive GCs. The total luminosities, colors and sizes of the UCDs are consistent with them being either luminous GCs or threshed nuclei of both early-type and late-type galaxies (not just early-type dwarfs). For the most luminous UCDs we estimate color gradients over a limited range of radius. These are systematically positive in the sense of getting redder outwards: mean Delta(F606W-F814W)=0.14 mag per 100 pc with rms=0.06 mag per 100 pc. The positive gradients found in the bright UCDs are consistent with them being either bright GCs or threshed early-type dwarf galaxies (except VUCD3). In contrast to the above results we find a very significant difference in the sizes of UCDs and early-type galaxy nuclei: the effective radii of UCDs are 2.2 times larger than those of early-type galaxy nuclei at the same luminosity. This result suggests an important test can be made of the threshing hypothesis by simulating the process and predicting what size increase is expected.